13
Problema de la mochila 0/1
Igual que en el tema anterior, pero los objetos no se pueden fragmentar en trozos más pequeños.
Problema: Tenemos n objetos, cada uno con un peso (wi) y un beneficio (vi), y una mochila en la que podemos meter objetos, con una capacidad de peso máximo M. El objetivo es maximizar el beneficio de los objetos transportados, donde cada objeto se puede coger entero (xi=1) o nada (xi=0).
Definición de la ecuación recurrente:
Sea Mochila (i, m) el problema de la mochila, considerando sólo los i primeros objetos (de los n originales) con una capacidad de peso m. Supondremos que devuelve el valor de beneficio total: ? xa·va
a=1..i
Podemos definir el problema de forma recurrente, en función de que se use o no el objeto i.
14
Problema de la mochila 0/1
Definición de la ecuación recurrente:
Si no se usa el objeto i: Mochila (i, m) = Mochila (i – 1, m)
Si se usa: Mochila (i, m) = vi + Mochila (i – 1, m – wi)
Valor óptimo:
Mochila (i, m) = max (Mochila (i-1, m), vi + Mochila (i-1, m – wi))
Casos base:
Si (i< 0) o (m< 0) entonces no hay solución: Mochila (i, m) = -?
En otro caso, si (i=0) ó (m=0) la solución es no incluir ningún objeto: Mochila (i, m) = 0
Definición de las tablas:
La solución del problema original será Mochila (n, M).
Por lo tanto necesitamos una tabla: V: array [0..n, 0..M] of integer.
V[i, j] = Beneficio máximo usando los i primeros objetos y peso j.
15
Problema de la mochila 0/1
Forma de rellenar las tablas:
Inicializar los casos base.
Para todo i, desde 1 hasta n, y j desde 1 hasta M, aplicar la ecuación de recurrencia:
V[i, j] = max (V[i – 1, j] , V[i – 1, j – wi] + vi)
Si j es negativo, entonces V[i, j] = -?, y el máximo será el otro término.
Ejemplo. n= 3, M= 6, w= (2, 3, 4), v= (1, 2, 5)
Tiempo de ejecución: ?(nM).
16
Problema de la mochila 0/1
Se puede tener una tabla auxiliar de 0/1 para almacenar las decisiones parciales y recomponer la solución, o
A partir de la tabla V obtener la solución (x1, x2, …, xn): partir de la posición V[n, M] y analizar las decisiones que se tomaron para cada objeto i.
Si (V[i, j] = V[i-1, j]) entonces la solución no usa el objeto i, xi= 0.
Si (V[i, j] = V[i-1, j-wi] + vi) entonces sí se usa el objeto i, xi= 1.
Si (V[i, j] = V[i-1, j-wi] + vi) y (V[i, j] = V[i-1, j]) entonces podemos usar el objeto i o no (existe más de una solución óptima).
Acabar cuando lleguemos a un i=0 ó j=0.
¿Cuál será el tiempo de recomponer la solución?
¿Se cumple el principio de optimalidad?
17
Multiplicación encadenada de matrices
Supongamos que tenemos las matrices M1, M2, …, Mn, que queremos multiplicar:
M = M1 x M2 x … x Mn
Puesto que el producto es asociativo, habrá muchas formas de realizar las multiplicaciones. Cada colocación de los paréntesis indica un orden en el que se realizan las operaciones.
Según el orden de las multiplicaciones, el número de total de multiplicaciones escalares necesarias puede variar considerablemente.
Sea una matriz A de dimensión pxq y B de qxr, entonces el producto AxB requiere p·q·r multiplicaciones escalares (método clásico).
18
Multiplicación encadenada de matrices
Ejemplo. Sean las matrices A, B, C y D, de dimensiones: A= 13×5, B= 5×89, C= 89×3 y D= 3×34. Podemos multiplicarlas de 5 formas:
((AB)C)D Requiere 10.582 = 13·5·89 + 13·89·3 + 13·3·34
(AB)(CD) " 54.201
(A(BC))D " 2.856 = 5·89·3 + 13·5·3 + 13·3·34
A((BC)D) " 4.055
A(B(CD)) " 26.418
Objetivo: obtener un orden de multiplicación que minimice el número de multiplicaciones escalares.
Solución sencilla: estimar el número de multiplicaciones necesarias para todas las ordenaciones posibles. Quedarse con la que tenga menor valor.
¿Cuál es el número de ordenaciones posibles, T(n)?
19
Multiplicación encadenada de matrices
Si n=1 ó n=2, T(n) = 1.
Si n>2, entonces podemos realizar la primera multiplicación por n-1 sitios distintos: (M1M2 … Mi)(Mi+1Mi+2… Mn)
T(n) = ? T(i)·T(n-i)
i=1..n-1
El valor de T(n) está en ?(4n/n2)
Para cada ordenación necesita un tiempo de ?(n).
Esta solución requeriría un tiempo con una cota inferior de ?(4n/n).
Solución utilizando programación dinámica
Definimos NMulti (i, j): el número mínimo de productos escalares necesarios para realizar la multiplicación entre la matriz i y la j (con i ? j), es decir: Mi x Mi+1 x … x Mj
Suponemos que las dimensiones se almacenan en un array d[0..n], donde la matriz Mi será de dimensión d[i-1] x d[i].
20
Multiplicación encadenada de matrices
Casos base:
Si i = j, entonces NMulti(i, j) = 0. No necesitamos realizar ninguna operación.
Si i = j-1, entonces NMulti(i, j) = d[i-1]·d[i]·d[i+1]. Sólo existe una forma de hacer el producto.
Ecuación de recurrencia:
Si no se da ninguno de los casos anteriores, entonces podemos hacer la primera multiplicación por una posición k, con i?k< j:
(Mi x … x Mk)x(Mk+1 x … X Mj)
El resultado será el valor mínimo:
NMulti(i, j) = min (NMulti(i, k) + NMulti(k+1, j) + d[i-1]·d[k]·d[j])
i?k< j
Tablas usadas por el algoritmo:
El resultado será NMulti(1, n).
Necesitamos una posición para cada i, j, con 1 ? i ? j ? n.
21
Multiplicación encadenada de matrices
Tablas usadas por el algoritmo.
Sea M una matriz [1..n, 1..n] de enteros. El algoritmo usará la mitad de la matriz.
Forma de rellenar la tabla.
Inicializar la matriz. Para todo i, desde 1 hasta n. M[i, i] = 0
Aplicar la ecuación de recurrencia por diagonales.
M[i, j] = min (M[i, k] + M[k+1, j] + d[i-1]·d[k]·d[j])
i?k< j
Ejemplo. n= 4, d = (10, 20, 50, 1, 100)
22
Multiplicación encadenada de matrices
¿Cuál es el orden de complejidad de este algoritmo?
En la posición M[1, n] tenemos almacenado el número mínimo de multiplicaciones escalares necesario (para la ordenación que es óptima). Necesitamos calcular cuál es esta ordenación óptima.
Usar una matriz auxiliar Mejork [1..n, 1..n] en la que se almacene el mejor valor de k encontrado en cada paso durante el cálculo de M (indica cuál fue el mínimo en cada celda).
En el ejemplo anterior.
 Página anterior | Volver al principio del trabajo | Página siguiente  |